package 中等.二分查找;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，
 * 且每个 starti 都 不同 。
 * 区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。
 * 返回一个由每个区间 i 的 右侧区间 在 intervals 中对应下标组成的数组。如果某
 * 个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-right-interval
 */
public class 寻找右区间_436 {

    public static void main(String[] args) {

        int[][] intervals = {{3, 4}, {2, 3}, {1, 2}};
        System.out.println(Arrays.toString(new 寻找右区间_436().findRightInterval(intervals)));

    }

    /**
     * 每个起点都不相同，遍历记录起点对应的索引
     * 排序+二分查找
     *
     * @param intervals
     * @return
     */
    public int[] findRightInterval(int[][] intervals) {
        int[] ans = new int[intervals.length];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < intervals.length; i++) {
            map.put(intervals[i][0], i);
        }
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);

        for (int i = 0; i < intervals.length; i++) {
            // interval=[1,1]时，自己也要算进去
            Integer tar = search(i, intervals[i][1], intervals);
            // 排序后打乱了顺序，需要用原索引顺序
            ans[map.get(intervals[i][0])] = tar == null ? -1 : map.get(tar);
        }
        return ans;
    }

    private Integer search(int left, int target, int[][] intervals) {
        int right = intervals.length - 1;
        Integer ans = null;
        while (left <= right) {
            int mid = right + (right - left) / 2;
            if (intervals[mid][0] >= target) {
                ans = intervals[mid][0];
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

}
